package com.data.basic.chapter11;

/** 利用森林结构表示结合，每一颗树表示一个集合，且当一个集合只有一个元素的时候，该元素的指针指向自己
 *
 * 这里的树结构 ，子节点指向父亲节点，根节点指向自己。             union(a,b)表示a的根节点指向b的根节点
 * @author wang on 2018/7/3.
 */
public class UnionFind2 implements UF {
    private int [] parent;

    public UnionFind2(int size) {
        this.parent = new int[size];
        for (int i=0;i<size;i++){
            parent[i] = i;
        }

    }
    public int getSize(){
        return parent.length;
    }

    //查找过程，查找元素p所对应的集合编号
    //查找根节点  时间复杂度O(h)
    private int find(int p){
        if (p<0||p>=parent.length){
            throw  new IllegalArgumentException("p is out of bound!");
        }
        while (p!=parent[p]){
            p = parent[p];
        }
        return p;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p)==find(q);
    }


    //时间复杂度O(h)
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot==qRoot){
            return;
        }
        parent[pRoot] = qRoot;

    }
}
